
Metric forensics a multi%2Dlevel approach for mining volatile graphs.

BASSET Scalable Gateway Finder in Large Graphs.

iPoG fast interactive proximity querying on graphs.

TANGENT a novel%2C %27Surprise me%27%2C recommendation algorithm.

Fast mining of complex time%2Dstamped events.
Given a collection of complex, time-stamped events, how do we find patterns and anomalies? Events could be meetings with one or more persons with one or more agenda items at zero or more locations (e.g., teleconferences), or they could be publications with authors,


GRAPHITE A Visual Query System for Large Graphs.
We present Graphite, a system that allows the user to visually construct a query pattern, finds both its exact and approximate matching subgraphs in large attributed graphs, and visualizes the matches. For example, in a social network where a person’s occupation is an attribute, the user can draw a ‘star ’ query for “finding a CEO who has interacted with a Secretary, a Manager, and an Accountant, or a structure very similar to this”. Graphite uses the G-Ray algorithm to run the query against a user-chosen data graph, gaining all of its benefits, namely its high speed, scalability, and its ability to find both exact and near matches. Therefore, for the example above, Graphite tolerates indirect paths between, say, the CEO and the Accountant, when no direct path exists. Graphite uses fast algorithms to estimate node proximities when finding matches, enabling it to scale well with the graph database size. We demonstrate Graphite’s usage and benefits using the DBLP author-publication graph, which consists of 356K nodes and 1.9M edges. A demo video of Graphite can be downloaded at
Using ghost edges for classification in sparsely labeled networks.
We address the problem of classification in partially labeled networks (a.k.a. within-network classification) where observed class labels are sparse. Techniques for statistical relational learning have been shown to perform well on network classification tasks by exploiting dependencies between class labels of neighboring nodes. However, relational classifiers can fail when unlabeled nodes have too few labeled neighbors to support learning (during training phase) and/or inference (during testing phase). This situation arises in realworld problems when observed labels are sparse. In this paper, we propose a novel approach to within-network classification that combines aspects of statistical relational learning and semi-supervised learning to improve classification performance in sparse networks. Our approach works by adding “ghost edges ” to a network, which enable the flow of information from labeled to unlabeled nodes. Through experiments on real-world data sets, we demonstrate that our approach performs well across a range of conditions where existing approaches, such as collective classification and semi-supervised learning, fail. On all tasks, our approach improves area under the ROC curve (AUC) by up to 15 points over existing approaches. Furthermore, we demonstrate that our approach runs in time proportional to L · E, where L is the number of labeled nodes and E is the number of edges.
Colibri fast mining of large static and dynamic graphs.
Low-rank approximations of the adjacency matrix of a graph are essential in finding patterns (such as communities) and detecting anomalies. Additionally, it is desirable to track the low-rank structure as the graph evolves over time, efficiently and within limited storage. Real graphs typically have thousands or millions of nodes, but are usually very sparse. However, standard decompositions such as SVD do not preserve sparsity. This has led to the development of methods such as CUR and CMD, which seek a nonorthogonal basis by sampling the columns and/or rows of the sparse matrix. However, these approaches will typically produce overcomplete bases, which wastes both space and time. In this paper we propose the family of Colibri methods to deal with these challenges. Our version for static graphs, Colibri-S, iteratively finds a nonredundant basis and we prove that it has no loss of accuracy compared to the best competitors (CUR and CMD), while achieving significant savings in space and time: on real data, Colibri-S requires much less space and is orders of magnitude faster (in proportion to the square of the number of non-redundant columns). Additionally, we propose an efficient update algorithm for dynamic, time-evolving graphs, Colibri-D. Our evaluation on a large, real network traffic dataset shows that Colibri-D is over 100 times faster than the best published competitor (CMD).
Proximity Tracking on Time%2DEvolving Bipartite Graphs.
Given an author-conference network that evolves over time, which are the conferences that a given author is most closely related with, and how do they change over time? Large time-evolving bipartite graphs appear in many settings, such as social networks, co-citations, market-basket analysis, and collaborative filtering. Our goal is to monitor (i) the centrality of an individual node (e.g., who are the most important authors?); and (ii) the proximity of two nodes or sets of nodes (e.g., who are the most important authors with respect to a particular conference?) Moreover, we want to do this efficiently and incrementally, and to provide “any-time ” answers. We propose pTrack and cTrack, which are based on random walk with restart, and use powerful matrix tools. Experiments on real data show that our methods are effective and efficient: the mining results agree with intuition; and we achieve up to 15∼176 times speed-up, without any quality loss. 1
Random walk with restart fast solutions and applications.

Fast Monitoring Proximity and Centrality on Time%2Devolving Bipartite Graphs.

Fast best%2Deffort pattern matching in large attributed graphs.
We focus on large graphs where nodes have attributes, such as a social network where the nodes are labelled with each person’s job title. In such a setting, we want to find subgraphs that match a user query pattern. For example, a ‘star ’ query would be, “find a CEO who has strong interactions with a Manager, a Lawyer, and an Accountant, or another structure as close to that as possible”. Similarly, a ‘loop ’ query could help spot a money laundering ring. Traditional SQL-based methods, as well as more recent graph indexing methods, will return no answer when an exact match does not exist. Our method can find exact-, as well as near-matches, and it will present them to the user in our proposed ‘goodness ’ order. For example, our method tolerates indirect paths between, say, the ‘CEO ’ and the ‘Accountant ’ of the above sample query, when direct paths do not exist. Its second feature is scalability. In general, if the query has nq nodes and the data graph has n nodes, the problem needs polynomial time complexity O(n nq), which is prohibitive. Our G-Ray (“Graph X-Ray”) method finds high-quality subgraphs in time linear on the size of the data graph. Experimental results on the DLBP author-publication graph (with 356K nodes and 1.9M edges) illustrate both the effectiveness and scalability of our approach. The results agree with our intuition, and the speed is excellent. It takes 4 seconds on average for a 4node query on the DBLP graph.
Fast direction%2Daware proximity for graph mining.
In this paper we study asymmetric proximity measures on directed graphs, which quantify the relationships between two nodes or two groups of nodes. The measures are useful in several graph mining tasks, including clustering, link prediction and connection subgraph discovery. Our proximity measure is based on the concept of escape probability. This way, we strive to summarize the multiple facets of nodes-proximity, while avoiding some of the pitfalls to which alternative proximity measures are susceptible. A unique feature of the measures is accounting for the underlying directional information. We put a special emphasis on computational efficiency, and develop fast solutions that are applicable in several settings. Our experimental study shows the usefulness of our proposed direction-aware proximity method for several applications, and that our algorithms achieve a significant speedup (up to 50,000x) over straightforward implementations.
Fast Random Walk with Restart and Its Applications.
How closely related are two nodes in a graph? How to compute this score quickly, on huge, disk-resident, real graphs? Random walk with restart (RWR) provides a good relevance score between two nodes in a weighted graph, and it has been successfully used in numerous settings, like automatic captioning of images, generalizations to the “connection subgraphs”, personalized PageRank, and many more. However, the straightforward implementations of RWR do not scale for large graphs, requiring either quadratic space and cubic pre-computation time, or slow response time on queries. We propose fast solutions to this problem. The heart of our approach is to exploit two important properties shared by many real graphs: (a) linear correlations and (b) blockwise, community-like structure. We exploit the linearity by using low-rank matrix approximation, and the community structure by graph partitioning, followed by the Sherman-Morrison lemma for matrix inversion. Experimental results on the Corel image and the DBLP dabasets demonstrate that our proposed methods achieve significant savings over the straightforward implementations: they can save several orders of magnitude in pre-computation and storage cost, and they achieve up to 150x speed up with 90%+ quality preservation. 1
Center%2Dpiece subgraphs problem definition and fast solutions.
Given Q nodes in a social network (say, authorship network), how can we find the node/author that is the centerpiece, and has direct or indirect connections to all, or most of them? For example, this node could be the common advisor, or someone who started the research area that the Q nodes belong to. Isomorphic scenarios appear in law enforcement (find the master-mind criminal, connected to all current suspects), gene regulatory networks (find the protein that participates in pathways with all or most of the given Q proteins), viral marketing and many more. Connection subgraphs is an important first step, handling the case of Q=2 query nodes. Then, the connection subgraph algorithm finds the b intermediate nodes, that provide a good connection between the two original query nodes. Here we generalize the challenge in multiple dimensions: First, we allow more than two query nodes. Second, we allow a whole family of queries, ranging from ’OR ’ to ’AND’, with ’softAND ’ in-between. Finally, we design and compare a fast approximation, and study the quality/speed trade-off. We also present experiments on the DBLP dataset. The experiments confirm that our proposed method naturally deals with multi-source queries and that the resulting subgraphs agree with our intuition. Wall-clock timing results on the DBLP dataset show that our proposed approximation achieve good accuracy for about 6: 1 speedup. This material is based upon work supported by the
GMine A System for Scalable%2C Interactive Graph Visualization and Mining.
Several graph visualization tools exist. However, they are not able to handle large graphs, and/or they do not allow interaction. We are interested on large graphs, with hundreds of thousands of nodes. Such graphs bring two challenges: the first one is that any straightforward interactive manipulation will be prohibitively slow. The second one is sensory overload: even if we could plot and replot the graph quickly, the user would be overwhelmed with the vast volume of information because the screen would be too cluttered as nodes and edges overlap each other. Our GMine system addresses both these issues, by using summarization and multi-resolution. GMine offers multi-resolution graph exploration by partitioning a given graph into a hierarchy of communities-within-communities and storing it into a novel R-tree-like structure which we name G-Tree. GMine offers summarization by implementing an innovative subgraph extraction algorithm and then visualizing its output. 1.
Generalized Manifold%2DRanking%2DBased Image Retrieval.
Abstract—In this paper, we propose a general transductive learning framework named generalized manifold-ranking-based image retrieval (gMRBIR) for image retrieval. Comparing with an existing transductive learning method named MRBIR [12], our method could work well whether or not the query image is in the database; thus, it is more applicable for real applications. Given a query image, gMRBIR first initializes a pseudo seed vector based on neighborhood relationship and then spread its scores via manifold ranking to all the unlabeled images in the database. Furthermore, in gMRBIR, we also make use of relevance feedback and active learning to refine the retrieval result so that it converges to the query concept as fast as possible. Systematic experiments on a general-purpose image database consisting of 5 000 Corel images demonstrate the superiority of gMRBIR over state-of-the-art techniques. Index Terms—Image retrieval, manifold ranking, outside the database, relevance feedback. I.
Graph based multi%2Dmodality learning.
To better understand the content of multimedia, a lot of research efforts have been made on how to learn from multi-modal feature. In this paper, it is studied from a graph point of view: each kind of feature from one modality is represented as one independent graph; and the learning task is formulated as inferring from the constraints in every graph as well as supervision information (if available). For semi-supervised learning, two different fusion schemes, namely linear form and sequential form, are proposed. For each scheme, it is derived from optimization point of view; and further justified from two sides: similarity propagation and Bayesian interpretation. By doing so, we reveal the regular optimization nature, transductive learning nature as well as prior fusion nature of the proposed schemes, respectively. Moreover, the proposed method can be easily extended to unsupervised learning, including clustering and embedding. Systematic experimental results validate the effectiveness of the proposed method.
A Unified Optimization Based Learning Method for Image Retrieval.
In this paper, an optimization based learning method is proposed for image retrieval from graph model point of view. Firstly, image retrieval is formulated as a regularized optimization problem, which simultaneously considers the constraints from low-level feature, online relevance feedback and offline semantic information. Then, the global optimal solution is developed in both closed form and iterative form, providing that the latter converges to the former. The proposed method is unified in the senses that 1) it makes use of the information from various aspects in a global optimization manner so that the retrieval performance might be maximally improved; 2) it provides a natural way to support two typical query scenarios in image retrieval. The proposed method has a solid mathematical ground. Systematic experimental results on a general-purpose image database demonstrate that it achieves significant improvements over existing methods.
Internet Traffic Prediction by W%2DBoost Classification and Regression.

Internet Traffic Prediction by W%2DBoost Classification and Regression.

Anomaly Internet Network Traffic Detection by Kernel Principle Component Classifier.
 As a crucial issue in computer network security, anomaly detection is receiving more and more attention from both application and theoretical point of view. In this paper, a novel anomaly detection scheme is proposed. It can detect anomaly network traffic which has extreme large value on some original feature by the major component, or does not follow the correlation structure of normal traffic by the minor component. By introducing kernel trick, the nonlinearity of network traffic can be well addressed. To save the processing time, a simplified version is also proposed, where only major component is adopted. Experimental results validate the effectiveness of the proposed scheme. 
Learning No%2DReference Quality Metric by Examples.
In this paper, a novel learning based method is proposed for No-Reference image quality assessment. Instead of examining the exact prior knowledge for the given type of distortion and finding a suitable way to represent it, our method aims to directly get the quality metric by means of learning. At first, some training examples are prepared for both high-quality and lowquality classes; then a binary classifier is built on the training set; finally the quality metric of an un-labeled example is denoted by the extent to which it belongs to these two classes. Different schemes to acquire examples from a given image, to build the binary classifier and to model the quality metric are proposed and investigated. While most existing methods are tailored for some specific distortion type, the proposed method might provide a general solution for No-Reference image quality assessment. Experimental results on JPEG and JPEG2000 compressed images validate the effectiveness of the proposed method. 1.
Multiple random walk and its application in content%2Dbased image retrieval.

Manifold%2Dranking based image retrieval.
In this paper, we propose a novel transductive learning framework named manifold-ranking based image retrieval (MRBIR). Given a query image, MRBIR first makes use of a manifold ranking algorithm to explore the relationship among all the data points in the feature space, and then measures relevance between the query and all the images in the database accordingly, which is different from traditional similarity metrics based on pair-wise distance. In relevance feedback, if only positive examples are available, they are added to the query set to improve the retrieval result; if examples of both labels can be obtained, MRBIR discriminately spreads the ranking scores of positive and negative examples, considering the asymmetry between these two types of images. Furthermore, three active learning methods are incorporated into MRBIR, which select images in each round of relevance feedback according to different principles, aiming to maximally improve the ranking result. Experimental results on a general-purpose image database show that MRBIR attains a significant improvement over existing systems from all aspects.
No%2Dreference quality assessment for JPEG2000 compressed images.
No-Reference quality assessment is a relatively new topic and has been attracting more and more attention in recent years. Due to the limited understanding of the human vision system, most of the existing methods focus on measuring to what extent the image has been distorted. In this paper, by viewing all edge points in JPEG2000 compressed images as ‘distorted ’ or ‘un-distorted’, we propose using principal component analysis (PCA) to extract the local feature of a given edge point, which indicates both blurring and ringing. We also propose using the probabilities of the given edge point being ‘distorted ’ and ‘un-distorted ’ to model the local distortion metric, which is straightforward and can be easily applied to any type of local feature. Experimental results demonstrate the effectiveness of our scheme. 1.

Blur detection for digital images using wavelet transform.
With the prevalence of digital cameras, the number of digital images increases quickly, which raises the demand for image quality assessment in terms of blur. Based on the edge type and sharpness analysis using Harr wavelet transform, a new blur detection scheme is proposed in this paper, which can determine whether an image is blurred or not and to what extent an image is blurred. Experimental results demonstrate the effectiveness of the proposed scheme. 1.

Mean version space a new active learning method for content%2Dbased image retrieval.
In content-based image retrieval, relevance feedback has been introduced to narrow the gap between low-level image feature and high-level semantic concept. Furthermore, to speed up the convergence to the query concept, several active learning methods have been proposed instead of random sampling to select images for labeling by the user. In this paper, we propose a novel active learning method named mean version space, aiming to select the optimal image in each round of relevance feedback. Firstly, by diving into the lemma that motivates support vector machine active learning method (SVM active), we come up with a new criterion which is tailored for each specific learning task and will lead to the fastest shrinkage of the version space in all cases. The criterion takes both the size of the version space and the posterior probabilities into consideration, while existing methods are only based on one of them. Moreover, although our criterion is designed for SVM, it can be justified in a general framework. Secondly, to reduce processing time, we design two schemes to construct a small candidate set and evaluate the criterion for images in the set instead of all the unlabeled images. Systematic experimental results demonstrate the superiority of our method over existing active learning methods.
Classification of Digital Photos Taken by Photographers or Home Users.
Abstract. In this paper, we address a specific image classification task, i.e. to group images according to whether they were taken by photographers or home users. Firstly, a set of low-level features explicitly related to such high-level semantic concept are investigated together with a set of general-purpose low-level features. Next, two different schemes are proposed to find out those most discriminative features and feed them to suitable classifiers: one resorts to boosting to perform feature selection and classifier training simultaneously; the other makes use of the information of the label by Principle Component Analysis for feature reextraction and feature de-correlation; followed by Maximum Marginal Diversity for feature selection and Bayesian classifier or Support Vector Machine for classification. In addition, we show an application in No-Reference holistic quality assessment as a natural extension of such image classification. Experimental results demonstrate the effectiveness of our methods. 1
Pseudo Relevance Feedback Based on Iterative Probabilistic One%2DClass SVMs in Web Image Retrieval.

Automatic Peak Number Detection in Image Symmetry Analysis
Abstract. In repeated pattern analysis, peak number detection in autocorrelation is of key importance, which subsequently determines the correctness of the constructed lattice. Previous work inevitably needs users to select peak number manually, which limits its generalization to applications in large image database. The main contribution of this paper is to propose an optimization-based approach for automatic peak number detection, i.e., we first formulate it as an optimization problem by a straightforward yet effective criterion function, and then resort to Simulated Annealing to optimize it. Based on this approach, we design a new feature to depict image symmetry property which can be automatically extracted for repeated pattern retrieval. Experimental results demonstrate the effectiveness of the optimization approach and the superiority of symmetry feature over wavelet feature in discriminating similar repeated patterns. 1
